package ch9;

import java.util.Arrays;

/**
 * @author oldliu
 * @since 1.0
 */
public class CharuPaixu {
    public static void main(String[] args) {
        int[] a = {9,4,39,-9,44,14,16,219,29};
        for(int i=1;i<a.length;i++){
            int temp=a[i];//暂存
            //0到i-1，已经是有序的，插入新值，保证还是有序
            int start=0;
            int end=i-1;

            while (start<=end){
                int mid=(start+end)/2;//中间位置
                if(a[mid]>temp)
                    end=mid-1;
                else
                    start=mid+1;
            }
            //start这个位置，就是temp的正确位置
            //从start 到 i-1后移一位
            for(int j=i-1;j>=start;j--){
                a[j+1]=a[j];
            }
            a[start]=temp;
        }
        System.out.println(Arrays.toString(a));
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
}
